import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class ValidParentheses {
    public boolean isValid(String s) {
        Map<Character, Character> pairs = new HashMap<>() {
            {
                put(')', '(');
                put('}', '{');
                put(']', '[');
            }
        };

        Stack<Character> stack = new Stack<>();
        char[] ch = s.toCharArray();
        for(char c : ch) {
            if(pairs.containsKey(c)) {
                if(stack.isEmpty() || stack.peek() != pairs.get(c)) {
                    // 如果栈为空, 或者 栈顶元素 与 当前 "右括号" 不匹配
                    return false;
                }
                // 如果是匹配的, 则出栈
                stack.pop();
            }else {
                // 不存在 c, 说明是 "左括号", 入栈
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}
